#ifndef _AVLTREE_H_
#define _AVLTREE_H_

#include <iostream>
#include <algorithm>
#include <vector>

#define ALLOWED_IMBALANCE 1

/**
* @brief To complete the class of AvlTree and complete the function.
* 
*/
template <typename Comparable>
class AvlTree
{
    private:

        /**
        * @brief To construct the fundamantal structure of AvlNode
        * 
        */
        struct AvlNode
        {
            Comparable element;
            AvlNode *left;
            AvlNode *right;
            int height;

            AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt )
                : element{ theElement }, left{ lt }, right{ rt }, height{ 0 } {}

            AvlNode( Comparable && theElement, AvlNode *lt, AvlNode *rt )
                : element{ std::move( theElement ) }, left{ lt }, right{ rt }, height{ 0 } {}
        };

        AvlNode *root;

        /**
         * Rotate binary tree node with left child.
         * For AVL trees, this is a single rotation for case 1.
         * Update heights, then set new root.
         */
        void rotateWithLeftChild( AvlNode * & k2 )
        {
            AvlNode *k1 = k2->left;
            k2->left = k1->right;
            k1->right = k2;
            k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
            k1->height = max( height( k1->left ), k2->height ) + 1;
            k2 = k1;
        }

        /**
         * Rotate binary tree node with right child.
         * For AVL trees, this is a single rotation for case 1.
         * Update heights, then set new root.
         */
        void rotateWithRightChild( AvlNode * & k2 )
        {
            AvlNode *k1 = k2->right;
            k2->right = k1->left;
            k1->left = k2;
            k2->height = max( height( k2->left ), height( k2->right )) + 1;
            k1->height = max( height( k1->right ), k2->height ) + 1;
            k2 = k1;
        }

        /**
         * Double rotate binary tree node: first left child
         * with its right child; then node k3 with new left child.
         * For AVL trees, this is a double rotation for case 2.
         * Update heights, then set new root.
         */
        void doubleWithLeftChild( AvlNode * & k3 )
        {
            rotateWithRightChild( k3->left );
            rotateWithLeftChild( k3 );
        }

        /**
         * Double rotate binary tree node: first left child
         * with its right child; then node k3 with new left child.
         * For AVL trees, this is a double rotation for case 2.
         * Update heights, then set new root.
         */
        void doubleWithRightChild( AvlNode * & k3 )
        {
            rotateWithLeftChild( k3->right );
            rotateWithRightChild( k3 );
        }

        /**
         * Make operation to keep balance of the AvlTree.
         * Update heights, then set new root.
         */
        void balance( AvlNode * & t )
        {
            if( t == nullptr )
                return;
            
            if( height( t-> left ) - height( t->right ) > ALLOWED_IMBALANCE )
                if( height( t->left->left ) >= height( t->left->right ) )
                    rotateWithLeftChild( t );
                else
                    doubleWithLeftChild( t );
            else if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )
                if( height( t->right->right ) >= height( t->right->left ))
                    rotateWithRightChild( t );
                else
                    doubleWithRightChild( t );
            
            t->height = max( height( t->left ), height( t->right )) + 1;
        }

        /**
         * Inner operation to insert the element
         */
        void insert( const Comparable & x, AvlNode * & t )
        {
            if( t == nullptr )
                t = new AvlNode{ x, nullptr, nullptr };
            else if( x < t->element )
                insert( x, t->left );
            else
                insert( x, t->right);

            balance( t );
        }

        /**
         * Inner operation to insert the element about some constant
         */
        void insert( Comparable && x, AvlNode * & t )
        {
            if( t == nullptr)
                t = new AvlNode{ std::move( x ), nullptr, nullptr };
            else if( x < t->element)
                insert( std::move( x ), t->left );
            else if( t->element < x )
                insert( std::move( x ), t->right );
            else
                ; // Duplicate; do nothing

            balance( t );
        }

        /**
         * Inner operation to find the maximal element of two numbers.
         */
        int max( const int a, const int b)
        {
            int max = ( a > b ) ? a : b;
            return max;
        }
        
        /**
         * Inner operation to remove the element x from t
         */
        void remove( const Comparable & x, AvlNode * & t )
        {
            if( t == nullptr )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != nullptr && t->right != nullptr ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                AvlNode *oldNode = t;
                t = ( t->left != nullptr ) ? t->left : t->right;
                delete oldNode;
            }

            balance( t );
        }
        
        /**
         * Inner operation to find the minimal element of the tree
         */
        AvlNode * findMin( const AvlNode *t ) const
        {
            if( t != nullptr )
                while( t->left != nullptr )
                    t = t->left;
            return t;
        }

        /**
         * Inner operation to find the maximal element of the tree
         */
        AvlNode * findMax( const AvlNode *t ) const
        {
            if( t != nullptr )
                while( t->right != nullptr )
                    t = t->right;
            return t;
        }

        /**
         * Inner operation to check whether the tree contains element x
         */
        bool contains( const Comparable & x, AvlNode *t )const
        {
            if( t == nullptr )
                return false;
            else if( x < t->element )
                return contains( x, t->left );
            else if( t->element < x )
                return contains( x, t->right );
            else
                return true;      //Mathch
        }

        /**
         * Inner operation to check whether the tree is empty
         */
        bool isEmpty( AvlNode * t ) const
        {
            if( t == nullptr)
                return true;
            else
                return false;
        }

        /**
         * Inner operation to get the height of the tree
         */
        int height( const AvlNode * t ) const
        {
            return ( t == nullptr ) ? -1 : t->height;
        }

        /**
         * Inner operation to clear the tree
         */
        void makeEmpty( AvlNode * & t )
        {
            if( t != nullptr )
            {
                makeEmpty( t->left );
                makeEmpty( t->right );
                delete t;
            }
            t = nullptr;
        }

        /**
         * Inner operation to print out the tree
         */
        void printTree( const AvlNode *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                std::cout << t->element << " ";
                printTree( t->right );
            }
        }

        /**
         * Inner operation to copy the tree
         */
        AvlNode * clone( AvlNode *t ) const
        {
            if( t == nullptr )
                return nullptr;
    
            return new AvlNode( t->element, clone( t->left ), clone( t->right ), t->height );
        }

        /**
         * Inner operation to recover the elements of tree into a vector
         */
        void recover( std::vector<Comparable> &_obj, AvlNode * t, int judge )
        {
            if( judge == 0)
                _obj.clear();
            if( t != nullptr)
            {
                recover( _obj, t->left, 1);
                _obj.push_back( t->element );
                recover( _obj, t->right, 1);
            }
        }

    public:

        /**
         * Creat an AvlTree
         */
        AvlTree( ) : root{ nullptr }
            {};

        /**
         * Creat an AvlTree by copy an old tree
         */
        AvlTree( const AvlTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        /**
         * Creat an AvlTree by copy a constant tree
         */
        AvlTree( AvlTree && rhs )
        {
            root.element = rhs.root.element;
            root.left = rhs.root.left;
            root.right = rhs.root.right;
            root.height = rhs.root.height;
            delete rhs.root;
        }

        /**
         * Clear and delete an AvlTree
         */
        ~AvlTree( )
        {
            makeEmpty( );
        }

        /**
         * Find the minimal element
         */
        const Comparable & finMin() const
        {
            return findMin( root )->element;
        }

        /**
         * Find the maximal element
         */
        const Comparable & finMax() const
        {
            return findMax( root )->element;
        }

        /**
         * Check wheher the tree contains element x
         */
        bool contains( const Comparable & x ) const
        {
            return contains( x, root );
        }

        /**
         * Check wheher the tree is empty
         */
        bool isEmpty() const
        {
            return isEmpty( root );
        }

        /**
         * Get the height of the tree
         */
        int height() const
        {
            return height( root );
        }

        /**
         * Print out the tree
         */
        void printTree() const
        {
            if( isEmpty( ) )
                std::cout << "Empty tree" << std::endl;
            else
                printTree( root );
        }

        /**
         * Clear the tree
         */
        void makeEmpty()
        {
            makeEmpty( root );
        }

        /**
         * Insert an element x
         */
        void insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**
         * Insert a constant element x
         */
        void insert( Comparable && x )
        {
            insert( x, root );
        }

        /**
         * Remove the element x
         */
        void remove( const Comparable & x )
        {
            remove( x, root );
        }

        /**
         * Redefine the function on " = " to copy an AvlTree
         */
        const AvlTree & operator=( const AvlTree & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }

        /**
         * Redefine the function on " = " to copy a constant AvlTree
         */
        AvlTree & operator=( const AvlTree && rhs )
        {
            this.root.element = rhs.root.element;
            this.root.left = rhs.root.left;
            this.root.right = rhs.root.right;
            this.root.height = this.root.height;
            delete rhs.root;
            return *this;
        }

        /**
         * Insert the elements into the AvlTree so that it is changed increasing.
         */
        void BST_sort( const std::vector<Comparable> &_obj )
        {
            if (root != nullptr)
                makeEmpty();
            int num = _obj.size();
            for (int i = 0; i < num; i++)
                insert( _obj[i], root );
        }

        /**
         * Copy the elements of AvlTree into vector
         */
        void recover( std::vector<Comparable> &_obj)
        {
            recover( _obj, root, 0 );
        }
};

#else
// Do nothing.
#endif